// //1.移动匹配还是暴力？解法,先判断第一个是否相等，使用flag标记，如果第一个相等再开始第二层循环。通过子串的长度来判断。
// var strStr = function(haystack, needle) {
//     for(let j = 0;j <haystack.length;j++) {
//         if(haystack[j]===needle[0]) {
//             let flag = true;
//             for(let i=1;i<needle.length;i++) {
//                 if(haystack[j+i]!=needle[i]) {
//                     flag = false;
//                     break;
//                 }
//             }
//             if(flag) {
//                 return j;
//             }
//         }
//     }
//     return -1;
// };

// KMP先求next数组

var strStr = function(haystack, needle) {
    let next = [0];
    let j = 0;//前缀末尾
    // i表示后缀首部
    for(let i = 1;i < needle.length;i++) {
        // 前后缀不相同，回退
        while(j>0&&needle[i]!==needle[j]) {
            j = next[j-1]
        }
        if(needle[i]===needle[j]){
            j++;
        }
        next[i] = j;
    }
// 2.使用next进行匹配
    let  jj = 0;
    for(let i = 0;i <haystack.length;i++) {
        while(jj>0&&haystack[i]!=needle[jj]) {
            jj = next[jj-1];
        }
        if(haystack[i]===needle[jj]) {
            jj++;
        }
        if(jj===needle.length) {
            return i-needle.length+1;
        }

    }
    return -1;
};

